#include <bits/stdc++.h>
using namespace std;

const int N = 605;
int g[N][N];
namespace stoerwagner
{
    int id[N];
    int add(int g[N][N], int a, int m)
    {
        static int S[N], scnt;
        static int cmp[N];
        static bool in[N];
        
        scnt = 0;
        memset(cmp, 0, sizeof(cmp[0]) * (m + 1));
        memset(in, 0, sizeof(in[0]) * (m + 1));

        S[scnt++] = id[a]; in[a] = 1;

        int mini = 0, minv = 0;

        while (scnt < m)
        {
            mini = -1; minv = -1;
            for (int i=1; i<=m; ++i)
            {
                if (in[i]) continue;
                cmp[i] += g[id[i]][S[scnt-1]];
                if (cmp[i] > minv)
                {
                    minv = cmp[i];
                    mini = i;
                }
            }
            S[scnt++] = id[mini];
            in[mini] = true;
        }

        int s = S[scnt-1], t = S[scnt-2];

        if (s > t) swap(s, t);
        for (int i=1; i<=m; ++i)
        {
            g[s][id[i]] += g[t][id[i]];
            g[id[i]][s] += g[t][id[i]];
            g[t][id[i]] = g[id[i]][t] = 0;
        }

        for (int i=1; i<=m; ++i)
        {
            if (id[i] == t)
            {
                for (int j=i+1; j<=m; ++j)
                    id[j-1] = id[j];
                break;
            }
        }
        return minv;
    }

    int go(int g[N][N], int n, int a = 1)
    {
        int m = n;
        for (int i=1; i<=m; ++i)
            id[i] = i;
        int ans = 0x7fffffff;
        for (; m > 1; --m)
        {
            ans = min(ans, add(g, a, m));
        }
        return ans;
    }
}

int n, m;


int main(int argc, char const *argv[])
{
    while (~scanf("%d%d", &n, &m))
    {
        for (int i=1; i<=n; ++i)
            memset(g, 0, sizeof(g[0]) * (n + 1));
        for (int i=1; i<=m; ++i)
        {
            int u, v, w;
            scanf("%d%d%d", &u, &v, &w);
            if (u == v) continue;
            g[u][v] += w;
            g[v][u] += w;
        }
        int ans = stoerwagner::go(g, n);
        printf("%d\n", ans);
    }
    
    
    return 0;
}
